package com.cty.tree;

/*
 *
 *
 * 二叉排序树
 *
 * */
public class BinarySortTree {
    private Node root;//头节点

    //添加方法
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    //寻找希望删除结点
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    //寻找希望删除结点的父结点
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    //功能：用于寻找右子树的最小结点的value并删除最小结点
    public int delRightTreeMin(Node node) {
        Node target = node;
        while (target.left != null) {
            target = target.left;
        }
        delNode(target.value);
        return target.value;
    }

    //功能：寻找左子结点的最大结点值
    public int delLeftTreeMax(Node node) {
        Node target = node;
        while (target.right != null) {
            target = target.right;
        }
        delNode(target.value);
        return target.value;
    }

    //删除结点
    public void delNode(int value) {
        if (root == null) {//空树
            return;
        } else {
            Node targetNode = search(value);
            if (targetNode == null) {//没找到退出
                return;
            }
            if (root.left == null && root.right == null) {//目标结点为root结点
                root = null;
                return;
            }
            Node parent = searchParent(value);
            if (targetNode.left == null && targetNode.right == null) {//目标结点为叶子结点
                if (parent.left != null && parent.left.value == value) {
                    parent.left = null;
                    return;
                } else if (parent.right != null && parent.right.value == value) {//非叶子结点，有两个子节点
                    parent.right = null;
                    return;
                }
            } else if (targetNode.left != null && targetNode.right != null) {//只有一个子结点
                int resVal = delRightTreeMin(targetNode.right);
//                    int resVal = delLeftTreeMax(targetNode.left);用左边的最大值替换
                targetNode.value = resVal;
                return;
            } else {//目标结点只有一颗子树
                if (targetNode.left != null) {
                    if (parent != null) {
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                            return;
                        } else {
                            parent.right = targetNode.left;
                            return;
                        }
                    } else {
                        root = targetNode.left;
                        return;
                    }
                } else {
                    if (parent != null) {
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                            return;
                        } else {
                            parent.right = targetNode.right;
                            return;
                        }
                    } else {
                        root  = targetNode.right;
                        return;
                    }
                }
            }
        }

    }


    //中序遍历
    public void midOrder() {
        if (root == null) {
            System.out.println("二叉排序树为空~");
        } else {
            root.midOrder();
        }
    }
}
